1. Field of the Invention
The present invention is related to integrated circuit design, and, more particularly, a method and system for mapping a Boolean logic network to a limited set of application-domain specific logic cells.
2. Field of the Related Art
Typical integrated circuit design environments make use of libraries of pre-designed standard cells (a cell library) which usually consist of from 500 cells to more than 1,000 cells. These libraries are composed of a number of simple, generic and standard logic functions that have been implemented in a form suitable for manufacturing. Each standard cell is a representation, typically the mask level representation, of the circuit that performs the logic function for that cell.
The logic functions performed by the cells in a typical cell library are intentionally general purpose and basic and the majority of them represent common, low-level logic functions such as AND, OR, XOR, AND-OR-INVERT (AOI), Multiplexer, Adder, etc. These are functions are representative of patterns that are recognized by logic designers, and those that are used as the building blocks for manual logic design. Full custom logic design at the transistor level can sometimes include complex AOI functions that are identifiable from their logic description, such as:(ā+ b)(c+d)But such functions are typically not included in standard cell libraries, and not representative of specific basic building blocks that are known to logic designers. Instead, they are more likely to be custom designed at the transistor level as an AOI gate.
In a typical integrated circuit (IC) design flow an IC design is translated to logic gates. In most cases this translation is performed by an automatic logic synthesis tool to derive a netlist based on a set of the aforementioned generic logic functions. This translation is often necessary as there are many different methods in common use for design specification. Those methods may include specification using a high-level programming language such as Verilog, VHDL or C or by manually entering schematics using a computer-aided design system.
As a high level language cannot be directly implemented into the physical layout of an integrated circuit, it is first converted to a gate level implementation. The result of the conversion is a representation of the design called a gate level netlist. This representation is usually in the form of simple logic functions such as NAND, NOR, etc. along with a representation of the connections between functions (the netlist).
Automatic logic synthesis tools are then generally used to bind a design to an implementation, based on a set of manufacturing technology specific logic cells from a cell library. The synthesis tool selects cells from the library based on a set of implementation goals that may include any combination of metrics related to area, performance or power and possibly manufacturing yield, to obtain a cell-based netlist. Logic synthesis, as is known, is generally the process of transformation of an RTL or a Boolean network such that its functionality is not altered into a form that is aligned for technology mapping.
Within the context of the conventional design flow as described above, techniques for optimization using regularity extraction have been proposed for designs dominated by datapaths, which are formed by a small number of repeating logic elements (or bit slices) that are interconnected in a very organized pattern, and other regular circuit structures including RAMs, PLAs, array multipliers etc. For such designs, identifying repeating regularity in circuits simplifies the effort required via synthesis, optimization and layout. However, such regularity extraction techniques rely on the assumption that the designs inherently have within them a high degree of regularity. For example, most of these techniques use information such as bus names and datapath features such as high-fanout control nets to identify repeating structures, such as bit slices. These techniques do not apply, therefore, to more general design flows and logic descriptions that are without such organization and repetition. Also, these techniques to identify repeating regularity do not modify the underlying structural or functional topology of the circuit, which further makes them ineffective for generalized logic and random logic applications.
In light of the above background, the typical commercial flow that is used in mapping a Boolean network to a set of technology-specific standard cell gates, is shown in FIG. 1. A Boolean network can be represented by a directed acyclic graph where each node is a Boolean function of one of three types: a primary input, internal, output. A Boolean network may not contain a directed cycle. Each internal node in a Boolean network represents a Boolean function of its fanins. A Boolean network may contain internal nodes with arbitrarily large number of fanins. The Boolean network is first decomposed into a subject graph (a graph which represents the design independent of a specific technology or library using simple logic primitives (most commonly AND and INV) to form the technology-independent netlist. Subsequently, the subject graph is then typically mapped to a cell library using structural/Boolean matching followed by binate covering against pre-stored patterns representing the cells in the library. As the cells in the library get more complex, the matching complexity increases exponentially. Moreover, this method suffers from a structure bias; i.e, the mapping quality is dependent on the subject graph structure which is often derived with little knowledge of the characteristics of the target cell library.